package practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Day39 {
    //两两交换链表的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode curNext = head.next;
        head.next = swapPairs(curNext.next);
        curNext.next = head;
        return curNext;
    }
    //合并K个链表
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2)->{
            return o1.val-o2.val;
        });
        for(ListNode node : lists) {
            if(node != null) {
                queue.offer(node);
            }
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(!queue.isEmpty()) {
            ListNode node = queue.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null) {
                queue.offer(node.next);
            }
        }
        return head.next;
    }
    //接雨水
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for(int i = 1; i < n-1; i++) {
            left[i] = Math.max(left[i-1],height[i-1]);
        }
        for(int i = n-2; i > 0; i--) {
            right[i] = Math.max(right[i+1],height[i+1]);
        }
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret += Math.max(0,Math.min(right[i],left[i])-height[i]);
        }
        return ret;
    }
    //N皇后
    List<List<String>> ret = new ArrayList<>();
    //左对角线
    boolean[] flag1;
    //右对角线
    boolean[] flag2;
    //列
    boolean[] col;
    int[] path;
    public List<List<String>> solveNQueens(int n) {
        flag1 = new boolean[2*n-1];
        flag2 = new boolean[2*n-1];
        col = new boolean[n];
        path = new int[n];
        dfs(0,n);
        return ret;
    }
    private void build(int n) {
        List<String> list = new ArrayList<>();
        for(int x : path) {
            char[] arr = new char[n];
            Arrays.fill(arr,'.');
            arr[x] = 'Q';
            list.add(new String(arr));
        }
        ret.add(list);

    }
    private void dfs(int r,int n) {
        if(r == n) {
            build(n);
        }
        //因为每一行只能有一个皇后,所以c代表列
        for(int c = 0; c < n; c++) {
            if(!col[c] && !flag1[r+c] && !flag2[r-c+n-1]) {
                path[r] = c;//r行c列有皇后
                col[c] = flag1[r+c] = flag2[r-c+n-1] = true;
                dfs(r+1,n);
                col[c] = flag1[r+c] = flag2[r-c+n-1] = false;
                path[r] = 0;
            }
        }
    }
    //最后一个正数
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            //首先先数组中所有非正数都转换成n+1
            if(nums[i] <= 0) {
                nums[i] = n+1;
            }
        }
        for(int i = 0; i < n; i++) {
            int j = Math.abs(nums[i]);
            if(j <= n && j-1 >=0) {
                nums[j-1] = -Math.abs(nums[j-1]);
            }
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;

    }
    //最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        text1 = " " + text1;
        text2 = " " + text2;
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
    //路径总和
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int pathSumFrom(TreeNode node, int sum) {
        if (node == null) return 0;
        return (node.val == sum ? 1 : 0)
                + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
    }
    //排序链表
    public ListNode sortList(ListNode head) {
        //其实就是一个归并排序
        //首先第一步找到中间节点，然后递归前边，和后边
        if(head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode cur = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(cur);

        //合并
        ListNode newHead = new ListNode(0);
        ListNode newCur = newHead;
        while(left != null && right != null) {
            if(left.val > right.val) {
                newCur.next = right;
                right = right.next;
            }else {
                newCur.next = left;
                left = left.next;
            }
            newCur = newCur.next;
        }
        if(left != null) {
            newCur.next = left;
        }
        if(right != null) {
            newCur.next = right;
        }
        return newHead.next;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode prev = newHead;
        ListNode cur = newHead;
        while (cur != null) {
            for (int i = 0; i < k && cur != null; i++) {
                cur = cur.next;
            }
            if (cur == null) {
                break;
            }
            ListNode curNext = cur.next;
            cur.next = null;
            ListNode start = prev.next;
            prev.next = reverse(start);
            start.next = curNext;
            prev = start;
            cur = start;
        }
        return newHead.next;

    }
    private ListNode reverse(ListNode root) {
        ListNode newHead = new ListNode(0);
        while(root != null) {
            ListNode curNext = root.next;
            root.next = newHead.next;
            newHead.next = root;
            root = curNext;
        }
        return newHead.next;
    }
}
